%
\documentclass[12pt]{article}
%\usepackage{german}
\usepackage{epsfig}
%\usepackage{12pt}
%\input{layout.sty}
%  a4.tex=210*297
%  a3.tex=297*420
\topmargin=-12mm         \textheight=236mm       % new:410-2*27=236
\oddsidemargin=-11mm     \evensidemargin=-11mm
\textwidth=170mm         % default:138mm new:296-2*27=242

\setlength{\parskip}{1.5ex plus0.5ex minus 0.5ex} % elastischer Absatz
\parindent0mm
%\pagestyle{plain}
%\pagestyle{empty}
\renewcommand{\arraystretch}{1.1} % zeilenabstand von arrays
\newcommand{\myframe}[1]{#1}
%\renewcommand{\baselinestretch}{2.0}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%M
%Buchstaben: sind Objekte bestehend aus zusammenhaengenden Punkten
%  der Farbe F=schwarz und anhaengender Randpunkte nahe F.
%
%Vorgehen:
% - Clusteranalyse, finden gleicher Buchstaben (Abstandsfunktion,Comprimierung)
%   - summer der Fehlerquadrate (best bei Gauss-rauschen)
% - Zeilenidentifizierung  
% - Identifizierung der Buchstaben, bester Vertreter+Fehler der anderen
% - Qualitaetsanalyse, Vergleich mit verrauschtem Bild etc.
\sloppy
\begin{document}
\begin{titlepage}
\title{GOCR-documentation}
\author{
 J\"org Schulenburg\thanks{Joerg.Schulenburg@physik.uni-magdeburg.de}
% \and
% coauthors
}
\date{Magdeburg, \today}
\maketitle
\begin{abstract}
In this documentation I describe some ideas for my OCR-program.
It contains algorithms and examples and gives you
 an impression of what the program can (or could) do.
\end{abstract}
\end{titlepage}
% \tableofcontents

\section{Introduction}
First I have to say that I am not a expert in pattern recognition 
or similar sings. My knowledge is based mostly on experiments with my
program.
Therefore do not worry about stupid algorithms I put in this document. 
In this documentation I describe some ideas for my OCR-program.
The examples give you an impression of how does the program handles 
your images. 
If you have comments regarding contents or spelling please
write to the author.

\section{List of ideas}
\subsection{Segmentation of textual regions / Layout analysis}
% Layout analysis
% Not implemented yet.
This is implemented as a recursiv division in two parts.
\begin{itemize}
\item look for the thickest horizontal or vertikal gap through the box
\item is the gap less than five times longer than thick do not divide  
\item do the same with the two new parts
\end{itemize}
I know that this algorithm is not as good as you wish,
but I do not know a better one.

 It would be very helpfull to know about a funtion which is able to
 decide whether the box represents a single text line or a more complex object. 

\subsection{Line detection} % better use row?
                            % ^matter of taste
%Line detection is done by looking for long horizontal lines not crossing
%black pixels. Unfortunately scanned images are often slightly rotated.
%Therefore, the program looks first only to the left half side.
%If a line is found, the first half of the right side is scanned, because
%the lines are often short. The difference in height gives an impression of the
%rotation angle. With this impression a second run detects the lines
%with more accuracy. If there is too much dust on the image, the line
%detection will fail.
 Lines of characters are detected by looking for interline spaces.
 these are characterized by a large number of non-black pixels in a
 row.  Image rotation presents a problem, therefore the program
 first looks only at the left half of the image.  When a line is
 found, the left half of the right side is scanned, because lines
 are often short.  The variation in height gives an indication of
 the rotation angle.  Using this angle, a second run detects lines
 more accurately.  Line detection may fail if there is dust on the
 image. 
 
 In version v0.2.3 this behaviour is slightly changed.
 To detect the rotation angle, the line through the most
 characters is detected.

\subsection{Cluster detection}
A cluster is a group of pixels which are connected with each other.
The simplest way to detect a cluster is to look for a pixel.
If you find one, look to the neighbouring pixels. This can be done recursively.
% The first pixel is the presenter of the cluster.

This method needs a lot of stack space if a cluster is very large,
and can cause problems with the memory.

Do you remember the algorithm for leaving a maze?
Go along the right (or left) wall. This seems to be a good approach
for detecting clusters without recursion.
The following picture shows a trace of the maze algorithm.

\begin{minipage}[b]{15cm}
\begin{verbatim}
first 35 steps     next 36 steps     
..@@@@@..@@@@<..   ..v<<<<..v<<<@..   * = starting point
..@@@@@@@@@.@^<.   ..>>v@^<<<@.@@@.   >^<v = go right,up,left,down
....@@@@@...@@^.   ....v@@@@...@@@.   @ = black pixel
....@@@@....@@^.   ....v@@@....@@@.
....@@@.....@@^.   ....v@@.....@@@.
....@@@.....@@^.   ....v@@.....@@@.
...@@@@.....@@^.   ...v<@@.....@@@.
...@@@......@@^.   ...v@@......@@@.
...@@@......@@^.   ...v@@......@@@.
...@@@.....@@@^.   ...v@@.....@@@@.
...@@@.....@@>^.   ...v@@.....@@@@.
...@@@.....@@^..   ...v@@.....@@@..
..@@@@.....@@^..   ..v<@@.....@@@..
..@@@@....@@@^..   ..v@@@....@@@@..
*>>>>>>>>>>>>^<<   @@@@@@@@@@@@@@@@
\end{verbatim}
\end{minipage}

The minimum and maximum coordinates can be used to create a box around the
cluster. But does this algorithm work with diagonally connected pixels?

\subsection{Engine}
How does the engine identify a character? For explanation look at the
following pattern.
The program looks for simple geometric properties. 

\begin{minipage}[b]{15cm}
\begin{verbatim}
vvvv         vv- white regions
......@@......  <- crossing one line
......@@......  
.....@@@@.....
.....@@@@.....
.....@@@@.....
....@..@@@....  <- white hole / crossing two lines
....@..@@@....  <- crossing two lines
....@..@@@....
...@....@@@...
...@....@@@...
...@....@@@...
..@@@@@@@@@@..  <- horizontal line near center
..@......@@@..
..@......@@@..  
.@........@@@.  v- increasing width of pattern
.@........@@@.  v
.@........@@@.  v
@@@......@@@@@
    ^^^-- gap

\end{verbatim}
\end{minipage}

In the future it should detect edges, verteces, gaps, angles and so on.
With such data the engine could make a cluster analysis.
But this is a difficult task, if the scanned image is noisy.


\subsection{Remove pixels}
The following picture shows a {\sl n} which has additional pixels at the
bottom. Therefore it can not be detected as {\sl n}. What can be done?
\begin{itemize}
\item classify horizontal ({\tt =}) and vertical ({\tt I}) pixels by
 comparing the distance between the next vertical and next horizontal white
 pixels (.)
\item measure mean thickness of vertical and horizontal clusters
\item erase unusually thin horizontal pixels at the bottom line
\end{itemize}

\begin{minipage}[b]{15cm}
\begin{verbatim}
..@@@@@..@@@@@..     ..==III..===II.. dx=16 dy=15
..@@@@@@@@@.@@@.     ..==III====.III. thickness 2 to 3
....@@@@@...@@@.     ....III==...III.
....@@@@....@@@.     ....III=....III.
....@@@.....@@@.     ....III.....III.
....@@@.....@@@.     ....III.....III.
...@@@@.....@@@.     ...IIII.....III.
...@@@......@@@.     ...III......III.
...@@@......@@@.     ...III......III.
...@@@.....@@@@.     ...III.....IIII.
...@@@.....@@@@.     ...III.....IIII.
...@@@.....@@@..     ...III.....III..
..@@@@.....@@@..     ..IIII.....III..
..@@@@....@@@@..     ..IIII....IIII..
@@@@@@@@@@@@@@@@     ================
      ^^^ 
      this causes the problem
\end{verbatim}
\end{minipage}

The next picture shows blind pixels which are caused by dust on the paper.
The upper right dots are not connected with the rest of the character.
This can be detected via fill-algorithms. Currently the program
assumes that dots near the upper end of a character are ``i''-dots
or diaereses (umlaut dots).

\begin{minipage}[b]{15cm}
\begin{verbatim}
..........................O...     ..........................O...
..........................O...     ..........................O...
..............................     ..............................
..............................     ..............................
..........@@@.......@@@@......     ..........@@@.......@@@@......
..@@@@..@@@@@@@...@@@@@@@.....     ..@@@@..@@@@@@@...@@@@@@@.....
@@@@@@@@@@@@@@@@.@@@@@@@@@....     @@@@@@@@@@@@@@@@.@@@@@@@@@....
..@@@@@@....@@@@@@.....@@@@...     ..@@@@@@....@@@@@@.....@@@@...
..@@@@.......@@@@......@@@@...     ..@@@@.......@@@@......@@@@...
..@@@@.......@@@.......@@@@...     ..@@@@.......@@@.......@@@@...
..@@@@.......@@@.......@@@@...     ..@@@@.......@@@.......@@@@...
..@@@@.......@@@.......@@@@...     ..@@@@.......@@@.......@@@@...
..@@@@.......@@@@......@@@@...     ..@@@@.......@@@@......@@@@...
..@@@@.......@@@.......@@@@...     ..@@@@.......@@@.......@@@@...
..@@@@.......@@@@......@@@@...     ..@@@@.......@@@@......@@@@...
..@@@@.......@@@.......@@@@...     ..@@@@.......@@@.......@@@@...
..@@@@.......@@@.......@@@@...     ..@@@@.......@@@.......@@@@...
..@@@@.......@@@.......@@@@...     ..@@@@.......@@@.......@@@@...
..@@@@.......@@@.......@@@@...     ..@@@@.......@@@.......@@@@...
..@@@@.......@@@.......@@@@...     ..@@@@.......@@@.......@@@@...
..@@@@.......@@@@......@@@@...     ..@@@@.......@@@@......@@@@...
..@@@@......@@@@@......@@@@@..     ..@@@@......@@@@@......@@@@@..
@@@@@@@@..@@@@@@@@@..@@@@@@@@@     @@@@@@@@..@@@@@@@@@..@@@@@@@@@
\end{verbatim}
\end{minipage}

\subsection{Add pixels}
The following picture shows a {\sl m}. The legs are only laxly connected.
% What can be done?
How do we handle this?
\begin{itemize}
\item if the engine has failed, a filter is switched on and the engine
 starts over
\item the 2x2 filter sets pixels to ({\sl O}) near laxly connected pixels
\end{itemize}

\begin{minipage}[b]{15cm}
\begin{verbatim}
   vv   vv
@@@.@@@..@@@...     @@@.@@@..@@@...
.@@.@@@@.@@@@..<    .@@O@@@@O@@@@..  filter: .@ => O@     @. => @O
.@@@..@@@..@@..<    .@@@..@@@..@@..          @. => @.     .@ => .@
.@@@..@@@..@@@.     .@@@..@@@..@@@.
.@@@..@@@..@@@.     .@@@..@@@..@@@.     
.@@@..@@@..@@@.     .@@@..@@@..@@@.     
.@@@..@@@..@@@.     .@@@..@@@..@@@.
.@@@..@@@..@@@.     .@@@..@@@..@@@.
.@@@..@@@..@@@.     .@@@..@@@..@@@.
.@@@..@@@..@@@.     .@@@..@@@..@@@.
.@@@..@@@..@@@.     .@@@..@@@..@@@.
.@@@..@@@..@@@.     .@@@..@@@..@@@.
.@@@..@@@..@@@.     .@@@..@@@..@@@.
@@@@@.@@@@.@@@@     @@@@@.@@@@.@@@@
\end{verbatim}
\end{minipage}

\subsection{Similarity analyzer}
Some characters are a little bit noisy. These characters can be identified by
comparison with other, already recognized characters. This can be done
via a good distance function.

\subsection{Overlapping characters}
The following picture shows an overlapping {\sl ru}.
%What can be done?
How do we handle this?
\begin{itemize}
\item look for 3 weak connections (sum over y is small, start in the middle)
\item test if the right and left part can be detected by the engine
\item correction of surrounding box
\end{itemize}

\begin{minipage}[b]{15cm}
\begin{verbatim}
....@@...@@@@@@@@@@....@@@@@@@..     ....@@...@@@@@@@@@@....@@@@@@@..
..@@@@..@@@@@..@@@@......@@@@@..     ..@@@@..@@@@@..@@@@......@@@@@..
@@@@@@@@@@@@@.,.@@@.......@@@@..     @@@@@@@@@@@@@...@@@.......@@@@..
..@@@@@@..@@@...@@@.......@@@@..     ..@@@@@@..@@@...@@@.......@@@@..
...@@@@.......,.@@@@......@@@@..     ...@@@@.........@@@@......@@@@..
...@@@@.........@@@@......@@@@..     ...@@@@.........@@@@......@@@@..
...@@@@.......,.@@@.......@@@@..     ...@@@@.........@@@.......@@@@..
...@@@@.........@@@.......@@@@..     ...@@@@.........@@@.......@@@@..
...@@@........,.@@@@......@@@@..     ...@@@..........@@@@......@@@@..
...@@@..........@@@@......@@@@..     ...@@@..........@@@@......@@@@..
...@@@........,.@@@@......@@@@..     ...@@@..........@@@@......@@@@..
...@@@..........@@@.......@@@@..     ...@@@..........@@@.......@@@@..
...@@@........,.@@@@......@@@@..     ...@@@..........@@@@......@@@@..
...@@@..........@@@@......@@@@..     ...@@@..........@@@@......@@@@..
...@@@........,.@@@@......@@@@..     ...@@@..........@@@@......@@@@..
...@@@..........@@@@@...@@@@@@@.     ...@@@..........@@@@@...@@@@@@@.
..@@@@@.......,..@@@@@@@@@.@@@@@     ..@@@@@..........@@@@@@@@@.@@@@@
@@@@@@@@@.........@@@@@@@..@@@..     @@@@@@@@@.........@@@@@@@..@@@..
..............,....@@@..........     ...................@@@..........
             ^^^
             213 weak vertical lines
 \end{verbatim}
\end{minipage}

Of course the situation is more difficult with slanted % geneigt
characters.
% Slanted characters pose more difficult problems.
\section{Tools}

\verb"pbmclean" ---
This program is written by Angus Duggan and Jef Poskanzer.
It cleans up ``snow'' on bitmap images.

\end{document}
%/*
% -----------------------------------------------------------------
%       #   v  
%       #   v     mark connected points via fifo-stack
%       ### *<<   and 3bit direction code per pixel,
%       # # ^ ^   should be better for overlapping letters
%       ### ^<<
% --------------------- point connections ----------------------
% searching next nearest point  
%     /----\
%     |    |
%   ^ | ## |
%   | | ## |
%   | |  | |
%   | \--/ |
%   \------/
%-------------------------------------------------------------
%*/
